package com.kaizen.leet538;

/**
 * @author undi
 * @date 2020/5/10
 * @description
 * 给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，使得每个节点的值是原来的节点值加上所有大于它的节点值之和。
 * 例如：
 * 输入: 原始二叉搜索树:
 *               5
 *             /   \
 *            2     13
 * 输出: 转换为累加树:
 *              18
 *             /   \
 *           20     13
 *  
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/convert-bst-to-greater-tree
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class SolutionUndi {
    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(5);

        treeNode.left = new TreeNode(2);
        treeNode.right = new TreeNode(13);
        System.out.println(convertBST(treeNode).toString());
    }

    private static int sum = 0;

    /**
     * 解法思路：降序遍历所有节点，先遍历左边或者右边
     * 遍历的时候将子节点的值与父节点相加
     * 对应官方方法1：回溯 -> 递归解法
     *
     * 1 ms  99.27%
     * 39.9 MB 80.00%
     *
     * @param root
     * @return
     */
    public static TreeNode convertBST(TreeNode root) {
        //判断根节点不为空，定义递归出口，保证递归直捣黄龙
        if (root != null) {
            //先访问右边的节点
            convertBST(root.right);
            //将右边的值累加到 sum 变量，将累加值赋值给根节点
            sum += root.val;
            root.val = sum;
            //访问左边的节点，进行同样的操作
            convertBST(root.left);
        }
        return root;
    }
}
